Map matching is a technique for determining a route based on location data received from one or more sensors. One type of location measuring mechanism, Global Positioning System (“GPS”), is widely used to determine real-time positioning of a particular person, vehicle, or any other entity capable of receiving a GPS signal. The location data received via GPS may be displayed on a digital map, which may include, for example, roads, buildings, and geographic landmarks. However, as GPS and digital maps are both prone to various errors, it is difficult to ensure that mobile positions identified via GPS are being registered properly on a digital map. As a result, an entity having a GPS sensor may be erroneously displayed on a digital map as moving through a building or moving across a body of water, or traversing an incorrect road. Although GPS data and other measured location data may not be entirely accurate, a map matching method may be useful for identifying a path or a road, for example, corresponding to the sensed geographic position. In addition, in response to receiving measured position data, a map matching method may further be utilized to reconstruct a route previously taken by an entity.
The road, path, and/or building identified by the map matching method may be inaccurate for a variety of reasons. For instance, in an urban setting, the map matching method may identify a plurality of streets in close proximity to the sensed position data. Therefore, for a vehicle having a GPS sensor, multiple candidate streets and measurement noise may make it difficult to determine the specific street being traversed. That is, a street identified as being the closest to the sensed position data might not be the street in which the vehicle is or was traveling. Moreover, simply matching each noisy sensed location point to the nearest path or road may also result in unreasonable and unlikely routes. If a real-time location displayed on a digital map is inaccurate, not only will a person be unaware of their respective location, but that person will also be unable to navigate to their final destination.